/*
 * @Author: liusheng
 * @Date: 2022-06-26 10:53:22
 * @LastEditors: liusheng
 * @LastEditTime: 2022-06-26 11:23:05
 * @Description: 剑指 Offer II 079. 所有子集
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 * 剑指 Offer II 079. 所有子集
给定一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

 

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：

输入：nums = [0]
输出：[[],[0]]
 

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同
 

注意：本题与主站 78 题相同： https://leetcode-cn.com/problems/subsets/

通过次数16,023  提交次数18,663
 */

#include "header.h"

/*
迭代法实现子集枚举
*/
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int len = nums.size();
        int setNum = 1 << len;
        vector<vector<int>> subsets;
        vector<int> subset;
        for (int mask = 0; mask < setNum; ++mask)
        {
            subset.clear();
            for (int j = 0; j < len; ++j)
            {
                if (mask & (1 << j))
                {
                    subset.push_back(nums[j]);
                }
            }

            subsets.push_back(subset);
        }

        return subsets;
    }
};

/*
方法二：递归法实现子集枚举
*/

class Solution {
public:
    /* 
    recursive dfs solution
    */
    vector<vector<int>> subsets(vector<int>& nums) {
        subsets(nums,0,{});
        return totalSets;
    }
private:
    /*
    cur:current index in nums
    */
    void subsets(vector<int>& nums,int cur,vector<int> prefix)
    {
        if (cur == nums.size())
        {
            totalSets.push_back(prefix);
            return;
        }

        //select current
        prefix.push_back(nums[cur]);
        subsets(nums,cur + 1,prefix);
        //not select current
        prefix.pop_back();
        subsets(nums,cur + 1,prefix);
    }
private:
    vector<vector<int>> totalSets;
};